The present invention relates to an error detecting circuit for detecting an error in received digital data containing a CRC (cyclic redundancy check) code.
In addition, the present invention relates to an error correcting circuit for correcting an error in received digital data containing a CRC code.
Moreover, the present invention relates to an error detecting method for detecting an error in received digital data containing a CRC code.
Furthermore, the present invention relates to an error correcting method for correcting an error in received digital data containing a CRC code.
Conventionally, in digital communications, a CRC code, such as CCITT CRC-16, is produced from transmit data and then added to the transmit data for transmission. On the receive side, an error in received data is corrected by means of an error trap method using the CRC code contained in the received data, thereby improving data transmission quality.
FIG. 1 shows a conventional error correcting circuit which uses the error trap method that corrects a single-bit error using a CCITT CRC-16-based CRC code. The error correcting circuit comprises a CRC coding circuit 10, a NOR circuit 20, an AND circuit, and a cyclic unit time delay circuit 40.
The CRC coding circuit 10, which is provided with a shift register consisting of 16 delay elements S0 to S15, divides received data represented by a receive polynomial Y(x) by the CRC generating polynomial G(x) of CCITT CRC-16 to obtain a residual polynomial S(x).
Assume here that transmit data is represented by a code polynomial W(x) and a single-bit error, E(x)=x.sup.i, has occurred in the transmit data during transmission. Then, the receive polynomial Y(x) will be represented by EQU Y(x)=W(x)+x.sup.i (1)
Coding by the CRC coding circuit 10 (division by the CRC generating polynomial G(x)) on the received data represented by the polynomial Y(x) forms a residual polynomial S(x) represented by EQU S(x)=[Y(x)]modG(x)=[x.sup.i ]modG(x) (2)
Assuming here that i&lt;degree G(x)=m, it is evident that the residual polynomial S(x) is x.sup.i. That is, the residual polynomial S(x) indicates an error polynomial (single-bit error).
When i.gtoreq.m, received data as shown in FIG. 2 is entered into the CRC coding circuit 10 to form a residual polynomial S(x). After that, 0s following the received data are entered into the CRC coding circuit until a single-bit error appears. Thus, cyclic replacement is made to detect and correct a single-bit error in the received data.
However, the error correction by the conventional error correcting circuit thus arranged requires calculations that correspond in number to the period generated by a shift register for the CRC generating polynomial irrespective of the length of received data, resulting in an increased delay time and consequently in an obstacle to real-time data communications.
To solve these problems, a parallel operation circuit has been used to reduce the calculation time. However, the use of the parallel operations circuit results in an increase in circuit scale.
With the conventional error detecting and correcting circuit, there occurs a delay that corresponds to the period of a CRC generating polynomial irrespective of the length of received data, resulting in an increase in the time required for error detection and correction. When a parallel operation circuit is used to solve this problem, a new problem will arise in that the circuit scale increases.